package demo4;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-25
 * Time: 23:00
 */
public class TestDemo {


//    //前缀树节点值
//    public static class Node1 {
//        public int pass;//经过的字符数量
//        public int end;//以这个字符结尾的数量
//        public Node1[] nexts;//相当于多叉树,每个节点都会有很多叉,最多的是根节点有可能有26个叉
//
//        // char tmp = 'b'  (tmp - 'a')
//        public Node1() {
//            //初始化每个节点的pass end为 0
//            pass = 0;
//            end = 0;
//            // 0    a - 'a'
//            // 1    b - 'a'
//            // 2    c
//            // ..   ..
//            // 25   z
//            // nexts[i] == null   i方向的路不存在
//            // nexts[i] != null   i方向的路存在
//            nexts = new Node1[26];//最对会有26个节点 -- 26个英文字符
//        }
//    }
//
//    public static class Trie1 {// -- 前缀树
//        private Node1 root;//每颗子树根节点
//
//        public Trie1() {//构造方法--刚开始创建一个根节点
//            root = new Node1();
//        }
//
//        public void insert(String word) {//将字符串插入到这颗前缀树
//            if (word == null) {//如果字符串为null,则返回不插入
//                return;
//            }
//            char[] str = word.toCharArray();//将字符串转换成字符数组
//            Node1 node = root;//刚开始node指向根节点
//            node.pass++;//在头结点经过一次 pass++
//            int path = 0;
//            for (int i = 0; i < str.length; i++) { // 从左往右遍历字符
//                path = str[i] - 'a'; // 由字符，对应成走向哪条路
//                if (node.nexts[path] == null) {//如果这条路没有被创建就创建出这条路
//                    node.nexts[path] = new Node1();
//                }
//                //不管是新创建的还是以前就有的只要经过这个节点都要进行pass++
//                node = node.nexts[path];//node要指向这条新的路的这个节点
//                node.pass++;//经过这个节点了就要++
//            }
//            node.end++;//最后到达这个字符串的结尾就要在末尾的字符的end++
//        }
//
//        public void delete(String word) {//删除此字符串
//            if (search(word) != 0) {//要在该字符串出现次数>0的情况下进行删除
//                char[] chs = word.toCharArray();//将字符串转换成字符数组
//                Node1 node = root;//该节点指向根节点
//                node.pass--;//走到根节点就要pass--证明当前字符串经过这个节点
//                int path = 0;
//                for (int i = 0; i < chs.length; i++) {//遍历这个字符数组
//                    path = chs[i] - 'a';//该字符该走向哪条路
//                    if (--node.nexts[path].pass == 0) {
//                        //如果发现当前字符经过次数--=0证明该节点的字符已经在tried树没了
//                        node.nexts[path] = null;//将其置为null GC回收
//                        return;
//                    }
//                    node = node.nexts[path];//否则指向当前路的这个节点
//                }
//                node.end--;//最后遍历到结尾字符要将end--
//            }
//        }
//
//        // word这个单词之前加入过几次
//        public int search(String word) {
//            if (word == null) {//如果字符串为null,将立即返回
//                return 0;
//            }
//            char[] chs = word.toCharArray();//将这个字符串转化成字符数组
//            Node1 node = root;//该节点指向根节点
//            int index = 0;
//            for (int i = 0; i < chs.length; i++) {
//                index = chs[i] - 'a';//该字符应该走向哪条路
//                if (node.nexts[index] == null) {//如果这条路为null就代表这棵trie没有这个字符串
//                    return 0;//立即返回
//                }
//                node = node.nexts[index];//否则node指向下一条路继续判断
//            }
//            return node.end;//当前节点也就是结尾的节点end就代表 从根节点一路到这个节点的出现次数
//        }
//
//        // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
//        public int prefixNumber(String pre) {
//            if (pre == null) {
//                return 0;
//            }
//            char[] chs = pre.toCharArray();
//            Node1 node = root;
//            int index = 0;
//            for (int i = 0; i < chs.length; i++) {
//                index = chs[i] - 'a';
//                if (node.nexts[index] == null) {
//                    return 0;
//                }
//                node = node.nexts[index];
//            }
//            return node.pass;//返回这个节点经过的次数就是前缀的数量
//        }
//    }
}
